package com.tyrone.algorithm.tree;

import com.tyrone.algorithm.linear.Queue;

public class BinaryTree<Key extends Comparable<Key>,Value>{
    //记录根结点
    private Node root;
    //记录树中元素的个数
    private int N;

    /**
     * 向树中插入一个键值对
     * @param key
     * @param value
     */
    public void put(Key key,Value value){
        root=put(root,key,value);
    }

    /**
     * 给指定树x上，添加键一个键值对，并返回添加后的新树
     * @param x
     * @param key
     * @param val
     * @return
     */
    private Node put(Node x, Key key, Value val){
        if (x==null){
            N++;
            return new Node(key,val,null,null);
        }
        int cmp = key.compareTo(x.key);
        if (cmp>0){
            x.right = put(x.right, key, val);
        }else if (cmp<0){
            x.left=put(x.left,key,val);
        }else {
            x.value=val;
        }
        return x;
    }


    /**
     * 根据key，从树中找出对应的值
     * @param key
     * @return
     */
    public Value get(Key key){
        return get(root,key);
    }

    /**
     * 从指定的树x中，找出key对应的值
     * @param x
     * @param key
     * @return
     */
    private Value get(Node x, Key key){
        if(x==null){
            return null;
        }
        int cmp = key.compareTo(x.key);
        if (cmp>0){
            return get(x.right,key);
        }else if(cmp<0){
            return get(x.left,key);
        }else {
            return x.value;
        }
    }

    /**
     * 根据key，删除树中对应的键值对
     * @param key
     */
    public void delete(Key key){
        root=delete(root,key);
    }

    /**
     * 删除指定树x上的键为key的键值对，并返回删除后的新树
     * @param x
     * @param key
     * @return
     */
    private Node delete(Node x, Key key){
        if (x==null){
            return null;
        }
        int cmp = key.compareTo(x.key);
        if (cmp>0){
            x.right = delete(x.right, key);
        }else if (cmp<0){
            x.left=delete(x.left,key);
        }else {
            N--;
            if (x.right==null){
                return x.left;
            }
            if (x.left==null){
                return x.right;
            }
            Node rightMin = x.right;
            while (rightMin.left!=null){
                rightMin=rightMin.left;
            }
            Node n = x.right;
            while (n.left!=null){
                if (n.left.left==null){
                    n.left=null;
                }else {
                    n=n.left;
                }
            }
            rightMin.left=x.left;
            rightMin.right=x.right;
            x=rightMin;

        }
        return x;
    }

    /**
     * 获取树中元素的个数
     * @return
     */
    public int size(){
        return N;
    }

    /**
     *  找出树中最小的键
     * @return
     */
    public Key min(){
        return min(root).key;
    }

    /**
     * 找出指定树x中，最小键所在的结点
     * @param x
     * @return
     */
    private Node min(Node x){
        if (x.left!=null){
            return min(x.left);
        }else {
            return x;
        }
    }

    /**
     * 找出树中最大的键
     * @return
     */
    public Key max(){
        return max(root).key;
    }

    /**
     * 找出指定树x中，最大键所在的结点
     * @param x
     * @return
     */
    public Node max(Node x){
        if (x.right!=null){
            return max(x.right);
        }else {
            return x;
        }
    }
    /**
     * 使用前序遍历，获取整个树中的所有键
     * @return
     */
    public Queue<Key> preErgodic(){
        Queue<Key> keys = new Queue<>();
        preErgodic(root,keys);
        return keys;
    }

    /**
     * 使用前序遍历，把指定树x中的所有键放入到keys队列中
     * @param x
     * @param keys
     */
    private void preErgodic(Node x, Queue<Key> keys){
        if (x==null)
            return;
        keys.enqueue(x.key);
        if (x.left!=null){
            preErgodic(x.left,keys);
        }
        if (x.right!=null){
            preErgodic(x.right,keys);
        }
    }

    /**
     * 使用中序遍历，获取整个树中的所有键
     * @return
     */
    public Queue<Key> midErgodic(){
        Queue<Key> keys = new Queue<>();
        midErgodic(root,keys);
        return keys;
    }

    /**
     * 使用中序遍历，把指定树x中的所有键放入到keys队列中
     * @param x
     * @param keys
     */
    private void midErgodic(Node x, Queue<Key> keys){
        if (x==null)
            return;
        if (x.left!=null){
            midErgodic(x.left,keys);
        }
        keys.enqueue(x.key);
        if (x.right!=null){
            midErgodic(x.right,keys);
        }
    }
    /**
     * 使用后序遍历，获取整个树中的所有键
     * @return
     */
    public Queue<Key> afterErgodic(){
        Queue<Key> keys = new Queue<>();
        afterErgodic(root,keys);
        return keys;
    }

    /**
     * 使用后序遍历，把指定树x中的所有键放入到keys队列中
     * @param x
     * @param keys
     */
    private void afterErgodic(Node x, Queue<Key> keys){
        if (x==null)
            return;
        if (x.left!=null){
            afterErgodic(x.left,keys);
        }
        if (x.right!=null){
            afterErgodic(x.right,keys);
        }
        keys.enqueue(x.key);
    }

    /**
     * 使用层序遍历，获取整个树中的所有键
     * @return
     */
    public Queue<Key> layerErgodic(){
        Queue<Key> keys = new Queue<>();
        Queue<Node> nodes = new Queue<>();
        nodes.enqueue(root);
        while (!nodes.isEmpty()){
            Node x = nodes.dequeue();
            keys.enqueue(x.key);
            if (x.left!=null){
                nodes.enqueue(x.left);
            }
            if (x.right!=null){
                nodes.enqueue(x.right);
            }
        }
        return keys;
    }

    /**
     * 计算整个树的最大深度
     * @return
     */
    public int maxDepth(){
        return maxDepth(root);
    }

    /**
     * 计算指定树x的最大深度
     * @param x
     * @return
     */
    private int maxDepth(Node x){
        if (x==null){
            return 0;
        }
        int max=0;
        int leftMax=0;
        int rightMax=0;
        if (x.left!=null){
            leftMax=maxDepth(x.left);
        }
        if (x.right!=null){
            rightMax=maxDepth(x.right);
        }
        max=leftMax>rightMax?leftMax+1:rightMax+1;
        return max;
    }


    private class Node{
        private Key key;

        private Value value;

        private Node left;

        private Node right;

        public Node(Key key,Value value,Node left,Node right){
            this.key=key;
            this.value=value;
            this.left=left;
            this.right=right;
        }

    }
}
